This invention relates to decoding information and more specifically to a method and apparatus for decoding information encoded using a linear cyclic block error correction code.
Linear codes form a linear vector space and include the property that two code words can be added using a suitable definition for addition to produce a third code word. In the case of a binary code, the operation is symbol-by-symbol modulo-2 addition of the code words, i.e. 1+1=0, 1+0=1, 0+1=1, 0+0=0. A code is a cyclic code if every cyclic shift of a code word generates another code word. An example of a linear cyclic block code is a Golay (23,12) code, i.e. n=23 bits long including k=12 data bits and (n-k)=11 redundancy bits.
Reliability and integrity of data communication over noisy and marginal (i.e. low signal-to-noise ratio) channels may be improved through use of error correction coding. Typically a parity word is attached to or concatenated with a data word to form a message or code word which is then transmitted. Conventional methods and apparatus for decoding code words, including linear cyclic block codes, are described in "Error-Correction Coding for Digital Communications" by George C. Clark, Jr. and J. Bibb Cain (1981) (hereinafter Clark and Cain) and "Error Control Coding: Fundamentals and Applications" by Shu Lin and Daniel J. Costello, Jr. (1983) (hereinafter Lin and Costello). These methods generally employ error trapping and/or algorithmic syndrome generation and begin decoding after the entire message word has been received. They are generally complex and expensive to implement since the entire decoding cycle must be repeated for each message word received. A maximum time interval or limit for completion of decoding may be imposed by overall system operating performance requirements and, in order to satisfy time constraints, expensive hardware decoder implementations may be required, especially for systems using bit serial transmission of the message word.
Accordingly it is an object of the present invention to provide a method and apparatus for reducing the time required for decoding linear cyclic block codes.
Another object of the present invention is to eliminate the need of expensive hardware for decoding linear cyclic block codes.
Still another object is to begin decoding a partially received string of information bits of a message word before the entire message word is received.